package datastructure.ch08_bst.ch04_add_in_bst;

import datastructure.ch08_bst.ch01_tree_base.node.TreeNode;

import java.util.Comparator;

/**
 * 
 *
 * @author guodd
 * @version 1.0 use jdk 1.8
 */
public class BinarySearchTree<E> {
    public static void main(String[] args) {
        BinarySearchTree<Integer> tree = new BinarySearchTree<>(Comparator.comparingInt(o -> o));

        tree.add(1);
        tree.add(5);
        tree.add(3);
    }

    /**
     * 属性描述：数量
     */
    private int size;

    private TreeNode<E> root;

    // 比较器
    final Comparator<E> comparator;

    public BinarySearchTree() {
        this(null);
    }

    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
    }

    public void add(E element) {
        elementNotNull(element);
        // 添加根节点
        if (root == null) {
            root = new TreeNode<>(element, null);
            size++;
            return;
        }
        // 非根节点
        // 1、查找父节点
        TreeNode<E> parent = root;
        TreeNode<E> node = root;
        // 方向
        int cmp = 0;
        while (node != null) {
            cmp = compare(element, node.element);
            parent = node;
            if (cmp > 0) {
                node = node.rightChild;
            } else if (cmp < 0) {
                node = node.leftChild;
            } else {
                // 覆盖还是直接return
                node.element = element;
            }
        }
        // 跳出while，说明node为null，那么parent是上一个node
        // 2、创建新节点
        TreeNode<E> newNode = new TreeNode<>(element, parent);
        if (cmp > 0) {
            parent.rightChild = newNode;
        } else {
            parent.leftChild = newNode;
        }
        size++;
    }

    private int compare(E e1, E e2) {
        // 如果比较强不为空，使用比较器的方法
        if (comparator != null) {
            return comparator.compare(e1, e2);
        }
        return ((Comparable<E>) e1).compareTo(e2);
    }


    public void remove(E element) {
        TreeNode<E> node = node(element);
        boolean isLeaf = node.isLeaf();
        // 1、叶子节点
        if (isLeaf) {
            int cmp = compare(node.element, node.parent.element);
            if (cmp > 0) {
                node.parent.rightChild = null;
            } else {
                node.parent.leftChild = null;
            }
            return;
        }
        // 2、度为2的节点
        boolean isTwo = node.isTwoChildren();
        if (isTwo) {

        }
        // 3、度为1的节点
    }

    public boolean contains(E element) {
        return false;
    }

    private void elementNotNull(E element) {
        if (element == null)
            throw new IllegalArgumentException("参数异常");
    }

    // 获取元素值对应的node
    private TreeNode<E> node(E element) {
        elementNotNull(element);
        TreeNode<E> node = root;
        while (node != null) {
            int cmp = compare(element, node.element);
            if (cmp == 0) return node;
            if (cmp > 0) {
                node = node.rightChild;
            } else {
                node = node.leftChild;
            }
        }
        return root;
    }

}
